{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# On-Site Question 2 - SOLUTION\n",
    "\n",
    "## Problem\n",
    "\n",
    "** Write a function that given a target amount of money and a list of possible coin denominations, returns the number of ways to make change for the target amount using the coin denominations**\n",
    "\n",
    "## Requirements\n",
    "\n",
    "** Write out your work on paper/pencil, then see if you can code up your solution **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "This is a classic interview problem, so classic that you've already seen a very similar problem in the recursion section! Make sure to review that problem first before reading our solution here!\n",
    "\n",
    "In this solution we will use a [bottom-up](https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design) algorithm.\n",
    "\n",
    "* As we iterate through each coin, we are adding the ways of making arr[i - coin] to arr[i]\n",
    "* If we have 2 ways of making 4, and are now iterating on a coin of value 3, there should be 2 ways of making 7.\n",
    "* We are essentially adding the coin we are iterating on to the number of ways of making arr[i]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solution(n, coins):\n",
    "    \n",
    "    # Set up our array for trakcing results\n",
    "    arr = [1] + [0] * n\n",
    "    \n",
    "    for coin in coins:\n",
    "        for i in range(coin, n + 1):\n",
    "            arr[i] += arr[i - coin]\n",
    "            \n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return arr[n]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "884"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution(100, [1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This solution results in O((m)(n)) with m being the number of coins, where we iterate about n operations. This is O(n) space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
